package __tree

import (
	"fmt"
	"math"
)
import stack "algorithm-go/4_stack"
import queue "algorithm-go/5_queue"

type Tree interface {
	Clear()
	Empty() bool
	// Depth 返回树的深度
	Depth() int
	// Root 返回根节点
	Root() int
	// Value 返回结点的值
	Value()
	// Assign 给结点赋值
	Assign()
	// Parent 若cur_e是树T的非根结点，则返回它的双亲，否则返回空
	Parent()
	// LeftChild 若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空
	LeftChild()
	// RightSibling 若cur_e有右兄弟，则返回它的右兄弟，否则返回空
	RightSibling()
	// InsertChild 其中p指向树T的某个结点，i为所指结点p的度加上1
	InsertChild()
	// DeleteChild 操作结果为删除T中p所指结点的第i棵子树
	DeleteChild()
}

type BiNode struct {

	// 数据
	data interface{}

	// 左右节点
	lNode, rNode *BiNode
}

// PreOrder 前序遍历
func (b *BiNode) PreOrder() {
	if b == nil {
		return
	}
	fmt.Print(b.data, " ")
	if b.lNode != nil {
		b.lNode.PreOrder()
	}
	if b.rNode != nil {
		b.rNode.PreOrder()
	}
}

// MiddleOrder 中序遍历
func (b *BiNode) MiddleOrder() {
	if b == nil {
		return
	}
	if b.lNode != nil {
		b.lNode.MiddleOrder()
	}
	fmt.Print(b.data, " ")
	if b.rNode != nil {
		b.rNode.MiddleOrder()
	}
}

// PostOrder 后序遍历
// 3 4 1 5 6 2 0
func (b *BiNode) PostOrder() {
	if b == nil {
		return
	}
	if b.lNode != nil {
		b.lNode.PostOrder()
	}
	if b.rNode != nil {
		b.rNode.PostOrder()
	}
	fmt.Print(b.data, " ")
}

// PreOrderUnRecur 非递归前序遍历
// 思路：使用栈结构，将头结点压入栈中，弹出并打印，依次压入弹出节点的右、左子节点，重复此步骤，直到栈为空
func (b *BiNode) PreOrderUnRecur() {
	if b == nil {
		return
	}
	s := stack.InitLinkStack()
	s.Push(b)
	var head *BiNode
	for !s.IsEmpty() {
		head = s.Pop().(*BiNode)
		fmt.Print(head.data)
		if head.rNode != nil {
			s.Push(head.rNode)
		}
		if head.lNode != nil {
			s.Push(head.lNode)
		}
	}
}

// MiddleOrderUnRecur 非递归中序遍历
// 思路：准备一个栈，先一次将每个左节点压入，弹出的时候打印并且压入该子节点的右节点，直到栈为空
func (b *BiNode) MiddleOrderUnRecur() {
	if b == nil {
		return
	}
	s := stack.InitLinkStack()
	head := b
	for !s.IsEmpty() || head != nil {
		if head != nil {
			s.Push(head)
			head = head.lNode
		} else {
			head = s.Pop().(*BiNode)
			fmt.Print(head.data)
			head = head.rNode
		}
	}
}

// PostOrderUnRecur 非递归后序遍历
// 思路：准备两个栈A和B，将头节点压入A栈中，弹出并打印，依次压入弹出节点的左、右子节点，并压入B栈中
// 最后弹出B栈中的数据
func (b *BiNode) PostOrderUnRecur() {
	if b == nil {
		return
	}
	s1 := stack.InitLinkStack()
	s2 := stack.InitLinkStack()
	head := b
	s1.Push(head)
	for !s1.IsEmpty() {
		head = s1.Pop().(*BiNode)
		s2.Push(head)
		if head.lNode != nil {
			s1.Push(head.lNode)
		}
		if head.rNode != nil {
			s1.Push(head.rNode)
		}
	}
	for !s2.IsEmpty() {
		fmt.Print(s2.Pop().(*BiNode).data)
	}
}

// WidthOrderUnRecur 非递归的层序遍历
// 思路：准备一个队列，放入头节点，然后出队，打印，再放左、右节点
// 找出最大宽度思路：
// 准备一个哈希表，记录每一个节点所在的层数，压入的时候记录
// 再准备三个变量：当前层，当前层的节点个数a，每一层的节点个数b
// 每一次弹出节点，比较当前层
// 每次循环找到 a 与 b 的最大值即可
func (b *BiNode) WidthOrderUnRecur() int {
	if b == nil {
		return -1
	}
	q := queue.NewSqQueue()
	q.EnQueue(b)
	levelMap := make(map[*BiNode]int)
	levelMap[b] = 1    // 记录头结点的层数
	curLevel := 1      // 当前层
	curLevelNodes := 0 // 当前层节点个数
	maxNodes := -1     // 最大的层节点数
	for !q.QueueEmpty() {
		// [1] = 2, cn = 1, cl=1
		n, err := q.DeQueue()
		if err != nil {
			panic(err)
		}
		node := n.(*BiNode)
		fmt.Print(node.data)
		// 将该节点的当前层与变量对比
		if levelMap[node] == curLevel {
			// 相等则增加 cn=1
			curLevelNodes++
		} else {
			// 不相等则重置变量，当前层增加，保存
			curLevel++
			maxNodes = int(math.Max(float64(maxNodes), float64(curLevelNodes)))
			curLevelNodes = 1
		}
		if node.lNode != nil {
			q.EnQueue(node.lNode)
			levelMap[node.lNode] = curLevel + 1
		}
		if node.rNode != nil {
			q.EnQueue(node.rNode)
			levelMap[node.rNode] = curLevel + 1
		}
	}
	maxNodes = int(math.Max(float64(maxNodes), float64(curLevelNodes)))
	return maxNodes
}
